package 图论述

/*
https://leetcode.cn/problems/rotting-oranges/?envType=study-plan-v2&envId=top-100-liked

994. 腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
示例 3：

输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
*/
func orangesRotting(grid [][]int) int {
	var rottens [][]int
	m, n := len(grid), len(grid[0])
	minutes, fresh := 0, 0 // 目前是多少分钟 新鲜橘子数量

	// 需要先把初始位置的烂橘子加入到rottens中，并统计新鲜橘子的数量
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				fresh++
			}
			if grid[i][j] == 2 {
				rottens = append(rottens, []int{i, j})
			}
		}
	}

	if len(rottens) == 0 && fresh == 0 { // 如果新鲜橘子和烂橘子的数量都为0，返回0
		return 0
	}
	if len(rottens) == 0 { // 如果没有烂橘子，直接返回即可
		return -1
	}

	// 将烂橙子的上下左右橙子都感染为烂橙子
	for len(rottens) > 0 && fresh > 0 {
		size := len(rottens) // 队列长度

		for i := 0; i < size; i++ { // 遍历烂橙子
			rotten := rottens[0] // 取出每个烂橙子的坐标
			rottens = rottens[1:]

			x, y := rotten[0], rotten[1]
			up, down, left, right := -1, -1, -1, -1

			if x-1 >= 0 { // 向上感染
				up = grid[x-1][y]
				if up == 1 { // 如果上面为新鲜橘子，进行感染
					fresh--
					grid[x-1][y] = 2
					rottens = append(rottens, []int{x - 1, y}) // 将新感染的橘子加入到下一轮烂橘子队列
				}
			}
			if x+1 < m { // 向下感染
				down = grid[x+1][y]
				if down == 1 { // 如果下面为新鲜橘子，进行感染
					fresh--
					grid[x+1][y] = 2
					rottens = append(rottens, []int{x + 1, y}) // 将新感染的橘子加入到下一轮烂橘子队列
				}
			}

			if y-1 >= 0 { // 向左感染
				left = grid[x][y-1]
				if left == 1 { // 如果左面为新鲜橘子，进行感染
					fresh--
					grid[x][y-1] = 2
					rottens = append(rottens, []int{x, y - 1}) // 将新感染的橘子加入到下一轮烂橘子队列
				}
			}
			if y+1 < n { // 向右感染
				right = grid[x][y+1]
				if right == 1 { // 如果右边为新鲜橘子，进行感染
					fresh--
					grid[x][y+1] = 2
					rottens = append(rottens, []int{x, y + 1}) // 将新感染的橘子加入到下一轮烂橘子队列
				}
			}
		}
		minutes++
	}

	if fresh > 0 {
		return -1
	} else {
		return minutes
	}
}
